package com.ljy.my_study.leetcode.到达目的地的第二短时间;

import java.util.*;

/**
 * @Description:
 * @Author: li.junying
 * @date: 2022-01-24 16:36
 */
public class TestMain2 {

    public int secondMinimum(int n, int[][] edges, int time, int change) {
        List<Integer>[] edgeArray=new List[n+1];
        for(int i=0;i<edges.length;i++){
            if(edgeArray[edges[i][0]]==null){
                edgeArray[edges[i][0]]=new ArrayList<>();
            }
            edgeArray[edges[i][0]].add(edges[i][1]);
        }
        int[][] paths=new int[n+1][2];
        for(int[] p:paths){
            Arrays.fill(p,Integer.MAX_VALUE);
        }
        paths[1][0]=0;
        Queue<int[]> queue=new LinkedList<>();
        queue.offer(new int[]{1,0});
        while(paths[n][1]==Integer.MAX_VALUE){
            int[] arr=queue.poll();
            int index=arr[0];
            int len=arr[1];
            for(int next:edgeArray[index]){
                if(len+1<paths[next][0]){
                    paths[next][0]=len+1;
                    queue.offer(new int[]{next,len+1});
                }else if(len+1>paths[next][0]&&len+1<paths[next][1]){
                    paths[next][1]=len+1;
                    queue.offer(new int[]{next,len+1});
                }
            }
        }
        int result=0;
        for(int i=0;i<paths[n][1];i++){
            if(result%(2*change)>=change){
                result+=(2*change-result%(2*change));
            }
            result+=time;
        }
        return result;
    }
}
